home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Entertainment / MacMud / Mud 4.0 / stralloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-16  |  7.0 KB  |  262 lines  |  [TEXT/MPS ]
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #include "config.h"
  5. #include "lint.h"
  6. #include "rc.h"
  7.  
  8. /*
  9.  * stralloc.c - string management.
  10.  *
  11.  * All strings are stored in an extensible hash table, with reference counts.
  12.  * free_string decreases the reference count; if it gets to zero, the string
  13.  * will be deallocated.  add_string increases the ref count if it finds a
  14.  * matching string, or allocates it if it cant.  There is no way to allocate
  15.  * a string of a particular size to fill later (hash wont work!), so you'll
  16.  * have to copy things freom a static (or malloced and later freed) buffer -
  17.  * that is, if you want to avoid space leaks...
  18.  *
  19.  * Current overhead:
  20.  *    8 bytes per string (next pointer, and 2 shorts for length and refs)
  21.  *    Strings are nearly all fairly short, so this is a significant overhead-
  22.  *    there is also the 4 byte malloc overhead and the fact that malloc
  23.  *    generally allocates blocks which are a power of 2 (should write my
  24.  *    own best-fit malloc specialised to strings); then again, GNU malloc
  25.  *    is bug free...
  26.  */
  27.  
  28. /*
  29.  * there is also generic hash table management code, but strings can be shared
  30.  * (that was the point of this code), will be unique in the table,
  31.  * require a reference count, and are malloced, copied and freed at
  32.  * will by the string manager.  Besides, I wrote this code first :-).
  33.  * Look at htable.c for the other code.  It uses the Hash() function
  34.  * defined here, and requires hashed objects to have a pointer to the
  35.  * next element in the chain (which you specify when you call the functions).
  36.  */
  37.  
  38. #define    MAXSHORT    (1 << (sizeof(short)*8 - 2))
  39. #define    WORD_ALIGN_BIT    0x3    /* these are 0 for aligned ptrs */
  40.  
  41. char * xalloc();
  42. #ifndef _AIX
  43. char * strcpy();
  44. #endif
  45.  
  46. static int num_distinct_strings = 0;
  47. int bytes_distinct_strings = 0;
  48. static int allocd_strings = 0;
  49. static int allocd_bytes = 0;
  50. int overhead_bytes = 0;
  51. static int search_len = 0;
  52. static int num_str_searches = 0;
  53.  
  54. /*
  55.  * strings are stored:
  56.  *    (char * next) (short numrefs) string
  57.  *                      ^
  58.  *                pointer points here
  59.  */
  60.  
  61. #define    NEXT(str)    (*(char **)((char *) (str) - sizeof(short)    \
  62.                            - sizeof(int)))
  63. #define    REFS(str)    (*(short *)((char *) (str) - sizeof(short)))
  64.  
  65. /*
  66.  * hash table - list of pointers to heads of string chains.
  67.  * Each string in chain has a pointer to the next string and a
  68.  * reference count (char *, int) stored just before the start of the string.
  69.  * HTABLE_SIZE is in config.h, and should be a prime, probably between
  70.  * 1000 and 5000.
  71.  */
  72.  
  73. static char ** base_table = 0;
  74.  
  75. void init_strings()
  76. {
  77.     int x;
  78.     base_table = (char **) xalloc(sizeof(char *) * HTABLE_SIZE);
  79.     overhead_bytes += (sizeof(char *) * HTABLE_SIZE);
  80.  
  81.     for (x=0; x<HTABLE_SIZE; x++)
  82.         base_table[x] = 0;
  83. }
  84.  
  85. /*
  86.  * generic hash function.  This is probably overkill; I haven't checked the
  87.  * stats for different prime numbers, etc.
  88.  */
  89.  
  90. static int StrHash(s)
  91. char * s;
  92. {
  93.     return hashstr(s, 20, HTABLE_SIZE);
  94. }
  95.  
  96. /*
  97.  * Looks for a string in the table.  If it finds it, returns a pointer to
  98.  * the start of the string part, and moves the entry for the string to
  99.  * the head of the pointer chain.  One thing (blech!) - puts the previous
  100.  * pointer on the hash chain into fs_prev.
  101.  */
  102.  
  103. char * findstring(s)
  104. char * s;
  105. {
  106.     char * curr, *prev;
  107.     int h = StrHash(s);
  108.  
  109.     curr = base_table[h];
  110.     prev = 0;
  111.     num_str_searches++;
  112.  
  113.     while (curr) {
  114.         search_len++;
  115.         if (*curr == *s && !strcmp(curr, s)) { /* found it */
  116.         if (prev) { /* not at head of list */
  117.             NEXT(prev) = NEXT(curr);
  118.             NEXT(curr) = base_table[h];
  119.             base_table[h] = curr;
  120.             }
  121.         return(curr);    /* pointer to string */
  122.         }
  123.         prev = curr;
  124.         curr = NEXT(curr);
  125.         }
  126.     
  127.     return(0); /* not found */
  128. }
  129.  
  130. /*
  131.  * Make a space for a string.  This is rather nasty, as we want to use
  132.  * alloc/free, but malloc overhead is generally severe.  Later, we
  133.  * will have to compact strings...
  134.  */
  135.  
  136. static char * alloc_new_string(string)
  137. char * string;
  138. {
  139.     char * s = xalloc(1 + strlen(string) + sizeof(char *) + sizeof(short));
  140.     int h = StrHash(string);
  141.  
  142.     s += sizeof(char *) + sizeof(short);
  143.     strcpy(s, string);
  144.     REFS(s) = 0;
  145.     NEXT(s) = base_table[h];
  146.     base_table[h] = s;
  147.     num_distinct_strings++;
  148.     bytes_distinct_strings += 4 + (strlen(s) +3) & ~3;
  149.     overhead_bytes += sizeof(char *) + sizeof(short);
  150.     return(s);
  151. }
  152.  
  153. char * make_shared_string(str)
  154. char * str;
  155. {
  156.     char * s;
  157.  
  158.     s = findstring(str);
  159.     if (!s)
  160.         s = alloc_new_string(str);
  161.     REFS(s)++;
  162.     allocd_strings++;
  163.     allocd_bytes += 4 + (strlen(str) + 3) & ~3;
  164.     return(s);
  165. }
  166.  
  167. /*
  168.  * free_string - reduce the ref count on a string.  Various sanity
  169.  * checks applied, the best of them being that a add_string allocated
  170.  * string will point to a word boundary + sizeof(int)+sizeof(short),
  171.  * since malloc always allocates on a word boundary.
  172.  * On systems where a short is 1/2 a word, this gives an easy check
  173.  * to see whather we did in fact allocate it.
  174.  *
  175.  * Don't worry about the overhead for all those checks!
  176.  */
  177.  
  178. /*
  179.  * function called on free_string detected errors; things return checked(s).
  180.  */
  181.  
  182. static void checked(s, str) char * s, *str;
  183. {
  184.     fprintf(stderr, "%s (\"%s\")\n", s, str);
  185.     fatal(s); /* brutal - debugging */
  186. }
  187.  
  188. void free_string(str)
  189. char * str;
  190. {
  191.     char * s;
  192.  
  193.     allocd_strings--;
  194.     allocd_bytes -= 4 + (strlen(str) + 3) & ~3;
  195.  
  196. #ifndef    BUG_FREE
  197. #ifdef    dcheck    /* GNU malloc range check flag */
  198.     { int align;
  199.     align = (((int)str) - sizeof(int) - sizeof(short)) & WORD_B_MASK;
  200.     if (align)
  201.         checked("Free string: improperly aligned string!", str);
  202.     }
  203. #endif /* dcheck */
  204. #endif
  205.  
  206.     s = findstring(str); /* moves it to head of table if found */
  207. #ifndef    BUG_FREE
  208.     if (!s) {
  209.         checked("Free string: not found in string table!", str);
  210.         return;
  211.     }
  212.     if (s != str) {
  213.         checked("Free string: string didnt hash to the same spot!", str);
  214.         return;
  215.     }
  216.  
  217.     if (REFS(s) <= 0) {
  218.         checked("Free String: String refs zero or -ve!", str);
  219.         return;
  220.     }
  221. #endif    /* BUG_FREE */
  222.  
  223.     if (REFS(s) > MAXSHORT) return;
  224.     REFS(s)--;
  225.     if (REFS(s) > 0) return;
  226.  
  227.     /* It will be at the head of the hash chain */
  228.     base_table[StrHash(str)] = NEXT(s);
  229.     num_distinct_strings--;
  230.     /* We know how much overhead malloc has */
  231.     bytes_distinct_strings-= 4 + (strlen(s) + 3) & ~3;
  232.     overhead_bytes -= sizeof(short) + sizeof(char *);
  233.     xfree(s-sizeof(short)-sizeof(char *));
  234.  
  235.     return;
  236. }
  237.  
  238. /*
  239.  * you think this looks bad!  and we didn't even tell them about the
  240.  * GNU malloc overhead!  tee hee!
  241.  */
  242.  
  243. int add_string_status(verbose)
  244.     int verbose;
  245. {
  246.     if (verbose) {
  247.     add_message("\nShared string hash table:\n");
  248.     add_message("-------------------------\t Strings    Bytes\n");
  249.     }
  250.     add_message("Strings malloced\t\t%8d %8d + %d overhead\n",
  251.         num_distinct_strings, bytes_distinct_strings, overhead_bytes);
  252.     if (verbose) {
  253.     add_message("Total asked for\t\t\t%8d %8d\n",
  254.             allocd_strings, allocd_bytes);
  255.     add_message("Space actually required/total string bytes %d%%\n",
  256.             (bytes_distinct_strings + overhead_bytes)*100 / allocd_bytes);
  257.     add_message("Searches: %d    Average search length: %6.3f\n",
  258.             num_str_searches, (double)search_len / num_str_searches);
  259.     }
  260.     return(bytes_distinct_strings + overhead_bytes);
  261. }
  262.